Batch 2 - Class 47- Pigeon Hole Principle II

Preclass Exercise:

MartinShCol - 1.15 - In a line up of 10 soldiers, what is the least number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height.
Answer: Mark every person by two numbers - the max number of consecutive ascending chain he is part of, and max descending chain he is part of. No two people can have same (asc,des) pair (WHY?), hence with 10 people, someone must have a "4" in at least one of ascending or descending tag.

Attendance: Tishyaa, Smiti, Diya, Muskaan, Aryan, Kabir, Anisha, Nandini, Aastha, Kushaan, Adit, Abhiram, Praharsh

Class Notes:

(MC - Chapter 4)

Revise basic pigeon hole principal. Pine trees problem, circular dinner table.

Generalized pigeon hole: If there are Nk+1 pigeons and N pigeon holes, then at least one pigeon hole must contain at least k+1 items.

There are M football teams with 11 players each. They are gathered at an airport to go for a game. There are 10 flights with room for exactly M players, and one player will take his own helicopter to the game. What is the minimum and maximum number of full teams that can reach the game?
1 and (10M+1)/11 quotient - For minimum, what is the pigeon and what is the pigeon hole?
Show that in any group of five people, there are two who have an identical number of friends within the group
Hint: What is the pigeon and what is the pigeon hole?Hint 2: Find two pigeon holes which cant be occupied simultaneously
Several football teams enter a tournament in which each team plays every other team exactly once. Show that at any moment, there will be at least two teams which have played an identical number of games.
Hint: Similar to last problem
What is the largest number of squares on an 8x8 chessboard which can be colored green, so that any tromino (three squares in L shape) has at least one non-green square?
Answer: 32 (divide into 16 2x2 squares - if any square has more than 2 green, then it will have a green tromino) - what is the pigeon and what is the pigeon hole?

Homework:

In the problem above, what is the smallest number of squares that can be colored green, so that every tromino has at least one green square?
Answer: 32 again! (in above 2x2 squares, with anything less than 32 greens, there will be a square with 0 or 1 green, hence a non-green tromino)

References:

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg

The Colossal Book of Short Puzzles and Problems, by Martin Gardner